
#[derive(PartialEq, Debug)]
pub struct Galaxie {
    row: usize,
    col: usize,
}

impl Galaxie {
    pub fn new(row: usize, col: usize) -> Self {
        Self { row, col }
    }
}

pub fn get_galaxies(image: &Vec<&str>) -> Vec<Galaxie> {
    let mut galaxies: Vec<Galaxie> = Vec::new();

    for (row, &line) in image.iter().enumerate() {
        for (col, ch) in line.chars().enumerate() {
            match ch {
                '#' => galaxies.push(Galaxie::new(row, col)),
                '.' => (),
                _   => panic!("nono"),
            }
        }
    }

    galaxies
}

pub fn get_empty_rows_position(image: &Vec<&str>) -> Vec<usize> {
    let mut empty_rows: Vec<usize> = Vec::new();
    let empty_row_str = ".".repeat(image.first().unwrap().len());

    for (row, &line) in image.iter().enumerate() {
        if empty_row_str == line {
            empty_rows.push(row);
        }
    }

    empty_rows 
}

pub fn get_empty_cols_position(image: &Vec<&str>) -> Vec<usize> {
    let mut empty_cols: Vec<usize> = Vec::new();

    let row_size = image.len();
    let col_size = image.first().unwrap().len();

    for c in 0..col_size {
        let mut empty_flag = true;
        for r in 0..row_size {
            let line: &str = image[r];
            if &line[c..c+1] == "#" {
                empty_flag = false;
                break;
            }
        }
        if empty_flag == true {
            empty_cols.push(c);
        }
    }

    empty_cols
}

pub fn c(n: usize, m: usize) -> Vec<Vec<usize>> {
    assert_ne!(n, 0);

    // C(n, m) = C(n - 1, m - 1) + C(n - 1, m)
    let mut result_vec: Vec<Vec<usize>> = Vec::new();
    if m == 0 {
        return vec![vec![]];
    }
    if m == 1 {
        for i in 0..n {
            result_vec.push(vec![i]);
        }
        return result_vec;
    }
    if n == m {
        let mut result: Vec<_> = Vec::new();
        for i in 0..n {
            result.push(i);
        }
        result_vec.push(result);
        return result_vec;
    }

    // C(n - 1, m - 1)
    let mut sub_result_vec1 = c(n - 1, m - 1);
    for sub_result in sub_result_vec1.iter_mut() {
        sub_result.push(n - 1);
    }

    // C(n - 1, m)
    let sub_result_vec2 = c(n - 1, m);

    // Combinds vec1 and vec2
    for sub_result in sub_result_vec2 {
        sub_result_vec1.push(sub_result);
    }

    sub_result_vec1
}

pub fn expand_image(galaxies: &mut Vec<Galaxie>, empty_rows: Vec<usize>, empty_cols: Vec<usize>) {
    let real_row = |row: usize| -> usize {
        let mut row_size = 0;
        for r in empty_rows.iter() {
            if row > *r {
                row_size += 1;
            }
        }
        if row_size == 0 { row } else { row + row_size * (EXPAND_RATIO - 1) }
    };

    let real_col = |col: usize| -> usize {
        let mut col_size = 0;
        for c in empty_cols.iter() {
            if col > *c {
                col_size += 1;
            }
        }
        if col_size == 0 { col } else { col + col_size * (EXPAND_RATIO - 1) }
    };

    for galaxie in galaxies {
        galaxie.row = real_row(galaxie.row);
        galaxie.col = real_col(galaxie.col);
    }
}

const EXPAND_RATIO: usize = 1000000;
pub fn get_steps_sum(galaxies: Vec<Galaxie>) -> usize {

    let delta = |v1: usize, v2: usize| -> usize {
        if v1 > v2 {
            v1 - v2
        } else {
            v2 - v1
        }
    };
    
    let get_step = |galaxie1: &Galaxie, galaxie2: &Galaxie| -> usize {
        let delta_row = delta(galaxie1.row, galaxie2.row);        
        let delta_col = delta(galaxie1.col, galaxie2.col);
        delta_col + delta_row 
    };
    
    let mut sum: usize = 0;
    let choises = c(galaxies.len(), 2);
    for choise in choises {
        assert!(choise.len() == 2);
        let &galaxie1_index = choise.get(0).unwrap();
        let &galaxie2_index = choise.get(1).unwrap();
        sum += get_step(
            &galaxies.get(galaxie1_index).unwrap(),
            &galaxies.get(galaxie2_index).unwrap()
        );
    }

    sum
}